In computer graphics, a computer is used to generate digital data that represents the projection of surfaces of objects in, for example, a three-dimensional scene, illuminated by one or more light sources, onto a two-dimensional image plane, to simulate the recording of the scene by, for example, a camera. The camera may include a lens for projecting the image of the scene onto the image plane, or it may comprise a pinhole camera in which case no lens is used. The two-dimensional image is in the form of an array of picture elements (which are variable termed “pixels” or “Pels”), and the digital data generated for each pixel represents the color and luminance of the scene as projected onto the image plane at the point of the respective pixel in the image plane. The surfaces of the objects may have any of a number of characteristics, including shape, color, specularity, texture, and so forth, which are preferably rendered in the image as closely as possible, to provide a realistic-looking image.
Generally, the contributions of the light reflected from the various points in the scene to the pixel value representing the color and intensity of a particular pixel are expressed in the form of the one or more integrals of relatively complicated functions. One rendering methodology, “global illumination,” includes a class of optical effects, such as indirect illumination, reflections off surfaces with various types of characteristics, such as diffuse, glossy and specular surfaces, caustics and color bleeding, which the are simulated in generating an image. In global illumination, a “rendering equation” is solved, which has a general form                               f          ⁡                      (            x            )                          =                              g            ⁡                          (              x              )                                +                                    ∫              0              1                        ⁢                                          K                ⁡                                  (                                      x                    ,                    y                                    )                                            ⁢                              f                ⁡                                  (                  y                  )                                            ⁢                                                           ⁢                              ⅆ                y                                                                        (        1        )            where “g” and “K” are known functions (“K” is sometimes referred to as the “kernel” of the integral equation), and “ƒ” is an unknown function. Generally, “ƒ(x)” represents the luminance at a particular point in the image from a particular direction and “g(x)” represents ambient illumination. The function “K,” is typically a complex function typically including factors such as characteristics of the objects' surfaces, such as the degree to which they are glossy, diffuse and/or specular, the angular relationships of surfaces with respect to each other, whether one surface is visible from another, and so forth. In connection with one aspect of simulation using ray tracing, in which an image as viewed by an observer is simulated by tracing rays, representing photons, between a light source and the eye of the observer, the unknown function “ƒ” can be obtained as                                           f            ⁡                          (              x              )                                =                    ⁢                                    g              ⁡                              (                x                )                                      +                                          ∫                0                1                            ⁢                                                K                  ⁡                                      (                                          x                      ,                                              x                        1                                                              )                                                  ⁢                                  g                  ⁡                                      (                                          x                      1                                        )                                                  ⁢                                  ⅆ                                      x                    1                                                                        +                                          ∫                0                1                            ⁢                                                ∫                  0                  1                                ⁢                                                      K                    ⁡                                          (                                              x                        ,                                                  x                          1                                                                    )                                                        ⁢                                      K                    ⁡                                          (                                                                        x                          1                                                ,                                                  x                          2                                                                    )                                                        ⁢                                      g                    ⁡                                          (                                              x                        2                                            )                                                        ⁢                                      ⅆ                                          x                      1                                                        ⁢                                      ⅆ                                          x                      2                                                                                            +                                          ∫                0                1                            ⁢                                                ∫                  0                  1                                ⁢                                                      ∫                    0                    1                                    ⁢                                                            K                      ⁡                                              (                                                  x                          ,                                                      x                            1                                                                          )                                                              ⁢                                          K                      ⁡                                              (                                                                              x                            1                                                    ,                                                      x                            2                                                                          )                                                              ⁢                                          K                      ⁡                                              (                                                                              x                            2                                                    ,                                                      x                            3                                                                          )                                                              ⁢                                          g                      ⁡                                              (                                                  x                          3                                                )                                                              ⁢                                          ⅆ                                              x                        1                                                              ⁢                                          ⅆ                                              x                        2                                                              ⁢                                          ⅆ                                              x                        3                                                              ⁢                                                                                   ⁢                    ⋯                                                                                      ⁢                                   ,                            (        2        )            if the series converges. The series is guaranteed to converge if       lim    ⁢                   ⁢          sup              n        →        ∞              ⁢                                    K          n                            n        <  1.
As described in the Grabenstein application, an approximation of the unknown function “ƒ” is obtained as follows. Defining the Heaviside function Θ(x) as                               Θ          ⁡                      (            x            )                          =                  {                                                                      1                  ,                                                                                                  for                    ⁢                                                                                   ⁢                    x                                    >                  0                                                                                                      0                  ,                                                                                                                        for                      ⁢                                                                                           ⁢                      x                                        ≤                    0                                    ,                                                                                        (        3        )            which will be referred to as a “Russian Roulette operator,” the “n-th” estimate of equation (2) is given by                                           f                          lds              ,              RR                                      (              n              )                                =                                    g              ⁡                              (                x                )                                      +                                          Θ                ⁡                                  (                                                            K                      ⁡                                              (                                                  x                          ,                                                      ξ                            1                                                          (                              n                              )                                                                                                      )                                                              -                                          ξ                      1                                              ′                        ⁡                                                  (                          n                          )                                                                                                      )                                            ⁢                              g                ⁡                                  (                                      ξ                    1                                          (                      n                      )                                                        )                                                      +                                          Θ                ⁡                                  (                                                            K                      ⁡                                              (                                                  x                          ,                                                      ξ                            1                                                          (                              n                              )                                                                                                      )                                                              -                                          ξ                      1                                              ′                        ⁡                                                  (                          n                          )                                                                                                      )                                            ⁢                              Θ                ⁡                                  (                                                            K                      ⁡                                              (                                                                              ξ                            1                                                          (                              n                              )                                                                                ,                                                      ξ                            2                                                          (                              n                              )                                                                                                      )                                                              -                                          ξ                      2                                              ′                        ⁡                                                  (                          n                          )                                                                                                      )                                            ⁢                              g                ⁡                                  (                                      ξ                    2                                          (                      n                      )                                                        )                                                      +                                          Θ                ⁡                                  (                                                            K                      ⁡                                              (                                                  x                          ,                                                      ξ                            1                                                          (                              n                              )                                                                                                      )                                                              -                                          ξ                      1                                              ′                        ⁡                                                  (                          n                          )                                                                                                      )                                            ⁢                                                           ⁢                              Θ                (                                                                   ⁢                                                      K                    ⁡                                          (                                                                        ξ                          1                                                      (                            n                            )                                                                          ,                                                  ξ                          2                                                      (                            n                            )                                                                                              )                                                        -                                      ξ                    2                                          ′                      ⁡                                              (                        n                        )                                                                                            )                            ⁢                                                           ⁢                              Θ                (                                                                   ⁢                                                      K                    ⁡                                          (                                                                        ξ                          2                                                      (                            n                            )                                                                          ,                                                  ξ                          3                                                      (                            n                            )                                                                                              )                                                        -                                      ξ                    3                                          ′                      ⁡                                              (                        n                        )                                                                                            )                            ⁢                                                           ⁢                              g                ⁡                                  (                                      ξ                    3                                          (                      n                      )                                                        )                                                      +            ⋯                          ⁢                                   ,                            (        4        )            where ξ1(n), . . . , ξL(n) and ξ′1(n), . . . , ξ′L(n) comprise “s”-dimensional low-discrepancy sequences, such as Halton sequences, which provide sample points in the s-dimensional unit cube [1,0)s for the respective estimation. Halton sequences are described in the Grabenstein application. The series in equation (4), which corresponds to equation (27) in the Grabenstein application, is used in connection with ray tracing in the direction from the image toward the light source(s), which is sometimes referred to as eye-to-light source ray tracing, where the image to be rendered simulates the image of a scene as would be seen by the eye of a person viewing the scene. In equation (4), the first summand of the series on the right-hand side (that is, the “g(x)” term) represents ambient illumination, the next summand (that is, the first “Θ” term) represents direct illumination, the next summand represents depth one reflection or refraction in the direction from the eye toward the light source, the next summand represents depth two reflection or refraction in the direction from the eye toward the light source, and so forth. The Russian Roulette operator essentially operates as a Russian Roulette check, and will guarantee that the series in equation (4) will eventually terminate at some summand, since eventually the value of one of the Russian Roulette operators Θ will equal zero, and that Russian Roulette operator Θ would also be in all subsequent terms of the series. Note that, in equation (4)
(i) each Russian Roulette check requires the evaluation of the kernel “K” at “x” and, respectively, ξ1(n), . . . , ξL(n), and
(ii) for the respective summands in equation (18), the value of function “g” that multiplies Θ in the summands is evaluated at different sample points ξ1(n), . . . , ξL(n).
As an alternative, if instead of using the image-to-light source ray tracing, the ray tracing is performed from the light source toward the image (which is sometimes referred to as light-to-eye ray tracing), the “n-th” estimation can be performed such that the value of the function “g” that multiply the Russian Roulette operator Θ in the summands is evaluated at one sample point, namely ξ1(n). In light source-to-eye ray tracing, instead of equation (2), the unknown function “ƒ” can be obtained as                                           f            ⁡                          (              x              )                                =                    ⁢                                    g              ⁡                              (                x                )                                      +                                          ∫                0                1                            ⁢                                                K                  ⁡                                      (                                          x                      ,                                              x                        1                                                              )                                                  ⁢                                  g                  ⁡                                      (                                          x                      1                                        )                                                  ⁢                                  ⅆ                                      x                    1                                                                        +                                          ∫                0                1                            ⁢                                                ∫                  0                  1                                ⁢                                                      K                    ⁡                                          (                                              x                        ,                                                  x                          2                                                                    )                                                        ⁢                                      K                    ⁡                                          (                                                                        x                          2                                                ,                                                  x                          1                                                                    )                                                        ⁢                                      g                    ⁡                                          (                                              x                        1                                            )                                                        ⁢                                      ⅆ                                          x                      1                                                        ⁢                                      ⅆ                                          x                      2                                                                                            +                                          ∫                0                1                            ⁢                                                ∫                  0                  1                                ⁢                                                      ∫                    0                    1                                    ⁢                                                            K                      ⁡                                              (                                                  x                          ,                                                      x                            3                                                                          )                                                              ⁢                                          K                      ⁡                                              (                                                                              x                            3                                                    ,                                                      x                            2                                                                          )                                                              ⁢                    K                    (                                          x                      2                                                                                                          ,                              x            1                    )                      g            ⁡                          (                              x                1                            )                                ⁢                      ⅆ                          x              1                                ⁢                      ⅆ                          x              2                                ⁢                      ⅆ                          x                              3                ⁢                                                                                                 ⁢                                           ⁢          ⋯                ⁢                                   ,                            (        5        )            which, in turn, can be estimated using                                                         f              _                                      lds              ,              RR                                      (              n              )                                ⁡                      (            x            )                          =                ⁢                              g            ⁡                          (              x              )                                +                                    K              ⁡                              (                                  x                  ,                                      ξ                    1                                          (                      n                      )                                                                      )                                      ⁢                          g              ⁡                              (                                  ξ                  1                                      (                    n                    )                                                  )                                              +                                    K              ⁡                              (                                  x                  ,                                      ξ                    2                                          (                      n                      )                                                                      )                                      ⁢                          Θ              ⁡                              (                                                      K                    ⁡                                          (                                                                        ξ                          2                                                      (                            n                            )                                                                          ,                                                  ξ                          1                                                      (                            n                            )                                                                                              )                                                        -                                      ξ                    1                                          ′                      ⁡                                              (                        n                        )                                                                                            )                                      ⁢                          g              ⁡                              (                                  ξ                  1                                      (                    n                    )                                                  )                                              +                                    K              ⁡                              (                                  x                  ,                                      ξ                    3                                          (                      n                      )                                                                      )                                      ⁢            Θ            (                          K              ⁡                              (                                                      ξ                    3                                          (                      n                      )                                                        ,                                      ξ                    2                                          (                      n                      )                                                                      )                                              -                                    ξ              2                              ′                ⁡                                  (                  n                  )                                                      )                          Θ              ⁡                              (                                                      K                    ⁡                                          (                                                                        ξ                          2                                                      (                            n                            )                                                                          ,                                                  ξ                          1                                                      (                            n                            )                                                                                              )                                                        -                                      ξ                    1                                          ′                      ⁡                                              (                        n                        )                                                                                            )                                      ⁢                          g              ⁡                              (                                  ξ                  1                                      (                    n                    )                                                  )                                              +                      ⋯            ⁢                                                   .                                              (        6        )            As with equation (4), the first summand of the series on the right-hand side (that is, the “g(x)” term) represents ambient illumination, and the next summand (that is, the first “Θ” term) represents direct illumination. In contrast with equation (4), the next summand represents depth one reflection or refraction in the direction from the light source toward the eye, the next summand represents depth two reflection or refraction in the direction from the light source toward the eye, and so forth. As with equation (4), the series in equation (6) will truncate since eventually the value of one of the Russian Roulette operators Θ will equal zero, and that Russian Roulette operator Θ would also be in all subsequent terms of the series. A comparison of equation (6) with equation (4) reveals that
(i) since the top line in equation (6) does not involve a Russian Roulette check, one fewer Russian Roulette check will typically be required than in equation (4); and
(ii) function “g” need only be evaluated at one sample point, namely, ξ1(n), reducing the amount of processing time required to generate each summand.
The methodology described above in connection with equations (1) through (6) generally assumes that the color is monochromatic. The invention provides an improved Russian Roulette methodology that allows for use in connection with a variety of colors and characteristics of surfaces of objects in the scene.